package primary.primary0;

/**
 *
 */
public class S0032最长有效括号 {



    class Solution {
        public int longestValidParentheses(String s) {
            int maxans = 0;
            // dp[i]表示以当前结尾的最长有效括号子串 注意是一定包括当前值，很多动态规划都有这个限制，强制包括当前值
            int[] dp = new int[s.length()];
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == ')') {
                    if (s.charAt(i - 1) == '(') {
                        // 左边是左括号，最多只能拼成 dp(i-2) + 2;
                        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                    } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        // 注意上面这个ifelse，如果 第二部分 不成立的话，dpi = 0，因为没办法凑成更长的括号

                        // 注意这里的 dp[i - dp[i - 1] - 2],像消消乐一样，当前i可能通过消掉一个(，让两块有效的括号连起来了。
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                    maxans = Math.max(maxans, dp[i]);
                }
                // 当前点是(的话dpi = 0;
            }
            return maxans;
        }
    }



    /**
     * 感觉可以用栈直接做出来, 但是栈只能找一个全程连续的括号, 多组符合的, 然后合并起来了的
     * 可以用一个数组记录一下每个位置的最大长度
     * 先把前面的)去掉
     */
    public int longestValidParentheses(String s) {

        char[] charList = s.toCharArray();
        int totalLen = charList.length;
        if(totalLen <= 1) return 0;
        int[] lenList = new int[totalLen];
        int startLoc = 0; // 前面的)需要被去掉
        for(char c: charList){
            if(c == ')'){
                startLoc ++;
            }else{
                break;
            }
        }
        for(int i = startLoc; i < totalLen; i++){
            if(charList[i] == '('){
                lenList[i] = 0;
            }else{
                recordLen(charList, lenList, i);
            }
        }

        return -1;
    }
    // 动态规划
    private void recordLen(char[] charList, int[] lenList, int loc){
        int toCompareLoc = loc - 1;
        // 处理((()()))这样被括起来的部分, 我们不用考虑被括起来的部分
        while(lenList[toCompareLoc] > 0){
            toCompareLoc = toCompareLoc - lenList[toCompareLoc];
            if(toCompareLoc < 0){
                // toCompareLoc = -1;
                lenList[loc] = loc;
                return;
            }
        }
        // ()(())这种情况, 就连续的可以直接处理, 两组括号合并怎么办
    }
}
